#include <algorithm>

struct avl_node_t {
    int         data;
    avl_node_t *left   = nullptr;
    avl_node_t *right  = nullptr;
    int         height = 0;

    avl_node_t(int data) : data(data) {}
    avl_node_t(int data, avl_node_t *left, avl_node_t *right)
            : data(data), left(left), right(right) {}
};

avl_node_t *LL(avl_node_t *root) {
    avl_node_t *node = root->left;
    root->left       = node->right;
    node->right      = root;

    root->height = std::max(root->left->height, root->right->height) + 1;
    node->height = std::max(node->left->height, root->height) + 1;

    return node;
}

avl_node_t *RR(avl_node_t *root) {
    avl_node_t *node = root->right;
    root->right      = node->left;
    node->left       = root;

    root->height = std::max(root->left->height, root->right->height) + 1;
    node->height = std::max(root->height, node->right->height) + 1;

    return node;
}

avl_node_t *LR(avl_node_t *root) {
    root->left = RR(root->left);
    return LL(root);
}

avl_node_t *RL(avl_node_t *root) {
    root->right = LL(root->right);
    return RR(root);
}

avl_node_t *insert(avl_node_t *root, int data) {
    if (!root) return new avl_node_t(data);

    if (data < root->data) {
        root->left = insert(root->left, data);

        if (root->left->height - root->right->height == 2) {
            if (data < root->left->data) {
                root = LL(root);
            } else {
                root = LR(root);
            }
        }
    } else if (data > root->data) {
        root->right = insert(root->right, data);

        if (root->left->height - root->right->height == -2) {
            if (data > root->right->data) {
                root = RR(root);
            } else {
                root = RL(root);
            }
        }
    }

    root->height = std::max(root->left->height, root->right->height) + 1;

    return root;
}
